package com.shm.leetcode;

import java.util.Arrays;

/**
 * @author: shm
 * @dateTime: 2020/11/14 9:10
 * @description: 1122. 数组的相对排序
 * 给你两个数组，arr1 和 arr2，
 *
 * arr2 中的元素各不相同
 * arr2 中的每个元素都出现在 arr1 中
 * 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
 *
 * 示例：
 *
 * 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
 * 输出：[2,2,2,1,4,3,3,9,6,7,19]
 *
 * 提示：
 *
 * arr1.length, arr2.length <= 1000
 * 0 <= arr1[i], arr2[i] <= 1000
 * arr2 中的元素 arr2[i] 各不相同
 * arr2 中的每个元素 arr2[i] 都出现在 arr1 中
 */
public class RelativeSortArray {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int n = arr1.length,m=arr2.length;
        boolean[] visited = new boolean[n];
        int[] ans = new int[n];
        int index = 0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(visited[j]){
                    continue;
                }else if(arr1[j]==arr2[i]){
                    ans[index]=arr1[j];
                    index++;
                    visited[j]=true;
                }
            }
        }
        int[] remain = new int[n-index];
        int k=0;
        for(int j=0;j<n;j++){
            if(!visited[j]){
                remain[k]=arr1[j];
                k++;
            }
        }
        Arrays.sort(remain);
        for(int i:remain){
            ans[index]=i;
            index++;
        }
        return ans;
    }

    /**
     * @author: shm
     * @dateTime: 2020/11/14 9:24
     * @description: 方法二：计数排序
     * 思路与算法
     *
     * 注意到本题中元素的范围为 [0, 1000][0,1000]，这个范围不是很大，我们也可以考虑不基于比较的排序，例如「计数排序」。
     *
     * 具体地，我们使用一个长度为 10011001（下标从 00 到 10001000）的数组 \textit{frequency}frequency，记录每一个元素在数组 \textit{arr}_1arr
     * 1
     * ​
     *   中出现的次数。随后我们遍历数组 \textit{arr}_2arr
     * 2
     * ​
     *  ，当遍历到元素 xx 时，我们将 \textit{frequency}[x]frequency[x] 个 xx 加入答案中，并将 \textit{frequency}[x]frequency[x] 清零。当遍历结束后，所有在 \textit{arr}_2arr
     * 2
     *   中出现过的元素就已经有序了。
     *
     * 此时还剩下没有在 \textit{arr}_2arr
     * 2
     *   中出现过的元素，因此我们还需要对整个数组 \textit{frequency}frequency 进行一次遍历。当遍历到元素 xx 时，如果 \textit{frequency}[x]frequency[x] 不为 00，我们就将 \textit{frequency}[x]frequency[x] 个 xx 加入答案中。
     *
     * 细节
     *
     * 我们可以对空间复杂度进行一个小优化。实际上，我们不需要使用长度为 10011001 的数组，而是可以找出数组 \textit{arr}_1arr
     * 1
     *   中的最大值 \textit{upper}upper，使用长度为 \textit{upper}+1upper+1 的数组即可。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(m + n + \textit{upper})O(m+n+upper)，其中 mm 和 nn 分别是数组 \textit{arr}_1arr
     * 1
     * ​
     *   和 \textit{arr}_2arr
     * 2
     * ​
     *   的长度，\textit{upper}upper 是数组 \textit{arr}_1arr
     * 1
     * ​
     *   中的最大值，在本题中 \textit{upper}upper 不会超过 10001000。遍历数组 \textit{arr}_2arr
     * 2
     * ​
     *   的时间复杂度为 O(n)O(n)，遍历数组 \textit{frequency}frequency 的时间复杂度为 O(\textit{upper})O(upper)，而在遍历的过程中，我们一共需要 O(m)O(m) 的时间得到答案数组。
     *
     * 空间复杂度：O(\textit{upper})O(upper)，即为数组 \textit{frequency}frequency 需要使用的空间。注意到与方法一不同的是，方法二的代码使用了额外的空间（而不是直接覆盖数组 \textit{arr}_1arr
     * 1
     * ​
     *  ）存放答案，但我们一般不将存储返回答案的数组计入空间复杂度，并且在我们得到数组 \textit{frequency}frequency 之后，实际上也是可以将返回答案覆盖在数组 \textit{arr}_1arr
     * 1
     * ​
     *   上的。如果在面试中遇到了本题，这些细节都可以和面试官进行确认。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/relative-sort-array/solution/shu-zu-de-xiang-dui-pai-xu-by-leetcode-solution/
     */
    public int[] relativeSortArray_2(int[] arr1, int[] arr2) {
        int n = arr1.length,m = arr2.length;
        int upper = 0;
        for (int value : arr1) {
            upper = Math.max(upper, value);
        }
        int[] frequency = new int[upper+1];
        for (int i : arr1) {
            frequency[i]++;
        }
        int[] ans = new int[n];
        int index = 0;
        for (int value : arr2) {
            for (int j = 0; j < frequency[value]; j++) {
                ans[index] = value;
                index++;
            }
            frequency[value] = 0;
        }
//        for (int i = 0; i < frequency.length; i++) {
//            if (frequency[i]>0){
//                for (int j = 0; j < frequency[i]; j++) {
//                    ans[index]=i;
//                    index++;
//                }
//            }
//        }
        for (int i = 0; i < frequency.length; i++) {
                for (int j = 0; j < frequency[i]; j++) {
                    ans[index]=i;
                    index++;
                }
        }
        return ans;
    }
}

